`
https://leetcode.cn/problems/open-the-lock/
`

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
  // 记录需要跳过的死亡数字
  const deads = new Set(deadends)
  // 如果死亡数字包括初始数字，不可能有结果
  if (deads.has('0000')) return -1

  // 记录已经访问过的数字
  const visited = new Set()
  // bfs 队列
  const q = ['0000']
  // 记录步数
  let step = 0

  while (q.length !== 0) {
    // 获取当前长度，本次 while 只循环当前层
    const len = q.length
    // 扩散所有可能
    for (let i = 0; i < len; i++) {
      // 获取数字
      const cur = q.shift()

      // 是否符合结果
      if (cur === target) return step

      // 将获取数字的所有下一个状态放入队列
      for (const neighbor of getNeighbors(cur)) {
        // 如果不是死亡数字，也没有访问过
        if (!deads.has(neighbor) && !visited.has(neighbor)) {
          // 将该数字放入队列
          q.push(neighbor)
          // 标记为已访问
          visited.add(neighbor)
        }
      }
    }
    // 每次遍历完该层，进入下一层时，步数加一
    step++
  }

  return -1
};

// 获取数字的所有下一个状态
const getNeighbors = (num) => {
  const neighbors = []
  for (let i = 0; i < num.length; i++) {
    // 获取所有上拨和下拨的状态
    neighbors.push(getUpNeighbor(num, i))
    neighbors.push(getDownNeighbor(num, i))
  }
  return neighbors
}

// 上拨 num[i]
const getUpNeighbor = (num, i) => {
  const _num = num.split('')
  if (_num[i] === '9') _num[i] = '0'
  else _num[i] = (+_num[i] + 1).toString()
  return _num.join('')
}

// 下拨 num[i]
const getDownNeighbor = (num, i) => {
  const _num = num.split('')
  if (_num[i] === '0') _num[i] = '9'
  else _num[i] = (+_num[i] - 1).toString()
  return _num.join('')
}